#include "binarytree.h"

//BTNode* BuyTreeNode(int x)
//{
//	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//	assert(node);
//	node->data = x;
//	node->left = NULL;
//	node->right = NULL;
//	return node;
//}
void Swap(BTDataType* p1, BTDataType* p2)
{
	BTDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(BTDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
//{
//	assert(a);
//	BTDataType* 
//	while (n > 1)
//	{
//		AdjustDown(a, n, pi);
//		pi = pi - 1;
//	}
//}


BTNode* BuyTreeNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTNode* CreatBinaryNode()
{
	BTNode* node1 = BuyTreeNode(1);
	BTNode* node2 = BuyTreeNode(2);
	BTNode* node3 = BuyTreeNode(3);
	BTNode* node4 = BuyTreeNode(4);
	BTNode* node5 = BuyTreeNode(5);
	BTNode* node6= BuyTreeNode(6);
	BTNode* node7 = BuyTreeNode(7);

	node1->left = node2;
	node2->left = node3;
	node1->right = node4;
	node4->left = node5;
	node4->right = node6;
	node5->left = node7;
	return node1;
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	;
}
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreePrevOrder(root->left);
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->right);
}
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

//void BinaryTreeLevelOrder(BTNode* root)
//{
//	assert(root);
//	BTNode* head = root;
//	BTNode* left = root;
//	BTNode* right = root;
//	while ()
//	{
//		printf("%d ", head->data);
//		left = head->left;
//		right = head->right;
//		if (left == NULL && right==NULL)
//			printf("N ");
//		head = head->left;
//		printf("%d ", head->data);
//		head = head->right;
//		printf("%d ", head->data);
//		head = head->left;
//
//	}
//}